#include "NFAToDFA.h"
#include "RegexpToPost.h"
#include "PostToNFA.h"
#include "NFAStateStack.h"
#include "NFAFragmentStack.h"

NFAFragmentStack FragmentStack; // ջ�����ڴ��� NFA Ƭ��
NFAStateStack StateStack;		// ջ�����ڴ��� NFA ״̬

const char VoidTrans = '$'; // ��ʾ��ת��


// char* regexp = "a(a|1)*";			 // �� 1
//char* regexp = "(aa|b)*a(a|bb)*"; // �� 2
char* regexp = "(a|b)*a(a|b)?"; 	 // �� 3

char regexp_ci[256];

int main(int argc, char **argv)
{
	char *post;
	DFA* dfa = (DFA*)malloc(sizeof(DFA));
	dfa->length = 0;
	
	//
	// ��ʼ��ջ
	//
	InitNFAFragmentStack(&FragmentStack);
	
	// �� CP Lab��ִ�г���ʱ����ʹ������궨������Ĵ��룬�ύ��ҵ��������������ˮ��ʱ������궨���ⲿ�ִ��롣
	// ����궨��������������ˮ��ʱ��input.txt�ļ��ж�ȡ�������ʽ��������������֤��
	// ���У�input1.txt �� input3.txt�ļ��а������������ʽ����1 �� ��3���������ʽ�Ƕ�Ӧ�ġ�
#ifdef CODECODE_CI
	scanf("%255s", regexp_ci);
	regexp = regexp_ci;  	 
#endif	
	
	//
	// ���� re2post �������������ʽ�ַ���ת���ɽ������ĺ����������
	//
	post = re2post(regexp);
	
	//
	// ���� post2dfa �������������ĺ����������ת��Ϊ DFA 
	//
	dfa = post2dfa(dfa, post);
	
	//
	// �� DFA ��ӡ���
	//
	OutputResult(dfa);
				
	return 0;
	
}

/*
���ܣ�
	����һ�� DFA ״̬��ת����
	
������
	TransformChar -- ת�����š�
	NFAStateArray -- NFA ״ָ̬�����顣
	Count -- ����Ԫ�ظ�����	
	  
����ֵ��
	 Transform �ṹ��ָ�롣
*/
Transform* CreateDFATransform(char TransformChar, NFAState** NFAStateArray, int Count)
{
	int i;
	Transform* pTransform = (Transform*)malloc(sizeof(Transform));
	
	for (i=0; i<Count; i++)
		pTransform->NFAlist[i] = NFAStateArray[i];
	
	pTransform->NFAStateCount = Count;	
	pTransform->TransformChar = TransformChar;
	pTransform->DFAStateIndex = -1;
	pTransform->NextTrans = NULL;
	
	return pTransform;
}

/*
���ܣ�
	����һ�� DFA ״̬��
	
������
	pTransform -- DFA ״̬ת��ָ�롣	
	  
����ֵ��
	 DFAState �ṹ��ָ�롣
*/
DFAState* CreateDFAState(Transform* pTransform)
{
	int i;
	DFAState* pDFAState = (DFAState*)malloc(sizeof(DFAState));
	
	for (i=0; i<pTransform->NFAStateCount; i++)
		pDFAState->NFAlist[i] = pTransform->NFAlist[i];

	pDFAState->NFAStateCount = pTransform->NFAStateCount;
	pDFAState->firstTran = NULL;

	return pDFAState;
}

/*
���ܣ�
	�ж�һ��ת���е� NFA ״̬�����Ƿ�Ϊĳһ�� DFA ״̬�� NFA ״̬���ϵ��Ӽ���
	
������
	pDFA -- DFA ָ�롣
	pTransform -- DFA ״̬ת��ָ�롣	
	  
����ֵ��
	 ������ڷ��� DFA ״̬�±꣬�����ڷ��� -1��
*/
int NFAStateIsSubset(DFA* pDFA, Transform* pTransform)
{
	//
	// TODO: �ڴ����Ӵ���
	//

	// ���ѭ������ DFA ����״̬
	for (int i = 0; i < pDFA->length; i++)
	{
		// DFA �е�ǰ״̬�� NFA ���ϻ��� < Transform ��Ԫ����, ������Ϊ���Ӽ�
		if (pDFA->DFAlist[i]->NFAStateCount < pTransform->NFAStateCount)
		{
			continue;
		}

		int count = 0;
		// �ڲ�ѭ������ pTransform ������NFA״̬
		for (int j = 0; j < pTransform->NFAStateCount; j++)
		{
			for (int k = 0; k < pDFA->DFAlist[i]->NFAStateCount; k++)
			{
				if (pDFA->DFAlist[i]->NFAlist[k]->Name == pTransform->NFAlist[j]->Name)
				{
					count++;
				}
				else
				{
					continue;
				}
			}
		}
		if (count == pTransform->NFAStateCount)
		{
			return i;
		}
	}
	return -1;
}

/*
���ܣ�
	�ж�ĳ�� DFA ״̬��ת���������Ƿ��Ѿ�����һ���ַ���ת����
	
������
	pDFAState -- DFAState ָ�롣
	TransformChar -- ת����ʶ����
	  
����ֵ��
	 Transform �ṹ��ָ�롣
*/
Transform* IsTransformExist(DFAState* pDFAState, char TransformChar)
{
	//
	// TODO: �ڴ����Ӵ���
	//
	Transform* ret = pDFAState->firstTran;

	while (ret != NULL)
	{
		if (ret->TransformChar == TransformChar)
		{
			return ret;
		}

		ret = ret->NextTrans;
	}
	return ret;
}

/*
���ܣ�
	��һ�� NFA ���Ϻϲ���һ�� DFA ת���е� NFA �����С�
	ע�⣬�ϲ���� NFA �����в�Ӧ���ظ��� NFA ״̬��
	
������
	NFAStateArray -- NFA ״ָ̬�����飬��������� NFA ���ϡ�
	Count -- ������� NFA ������Ԫ�ظ�����
	pTransform -- ת��ָ�롣
*/
void AddNFAStateArrayToTransform(NFAState** NFAStateArray, int Count, Transform* pTransform)
{
	//
	// TODO: �ڴ����Ӵ���
	//
	int i = 0, j;

	for (; i < Count; i++)
	{
		int theSame = 0;
		for (j = 0; j < pTransform->NFAStateCount; j++)
		{
			if (NFAStateArray[i]->Name == pTransform->NFAlist[j]->Name)
			{
				theSame=1;
				break;		
			}
		}
		if (theSame==1)
		{
			continue;
		}

		pTransform->NFAlist[pTransform->NFAStateCount] = NFAStateArray[i];
		pTransform->NFAStateCount++;
	}
}

/*
���ܣ�
	ʹ�ö���������������㷨��һ�� NFA ״̬�Ħ�-�հ���
	
������
	State -- NFA ״ָ̬�롣�Ӵ� NFA ״̬��ʼ���-�հ���
	StateArray -- NFA ״ָ̬�����顣���ڷ��ئ�-�հ���
	Count -- Ԫ�ظ�����	���ڷ��ئ�-�հ��� NFA ״̬�ĸ�����
*/
void Closure(NFAState* State, NFAState** StateArray, int* Count)
{
	InitNFAStateStack(&StateStack); // ���� InitNFAStateStack ������ʼ��ջ
	
	*Count=0;
	//
	// TODO: �ڴ����Ӵ���
	//
	while (State!=NULL || NFAStateStackEmpty(&StateStack) != 1)
	{
		while (State!=NULL)
		{
			PushNFAState(&StateStack, State);
			StateArray[*Count] = State;
			(*Count)++;

			if (State->Transform == VoidTrans)
			{
				State=State->Next1;
			}
			else
			{
				State=NULL;
			}
		}
		State=PopNFAState(&StateStack);
		if (State->Transform == VoidTrans)
		{
			State=State->Next2;
		}
		else
		{
			State=NULL;
		}
	}
}

/*
���ܣ�
	���������ĺ����������ת��Ϊ DFA��

������
	pDFA -- DFA ָ�롣
	postfix -- �������ʽ�Ľ���������������С�
	  
����ֵ��
	DFA ָ�롣
*/
NFAState* Start = NULL;
DFA* post2dfa(DFA* pDFA, char *postfix)
{
	int i, j;								// �α�
	Transform* pTFCursor;  					// ת��ָ��
	NFAState* NFAStateArray[MAX_STATE_NUM]; // NFA ״ָ̬�����顣���ڱ����-�հ�
	int Count = 0;							// ��-�հ���Ԫ�ظ���
	
	//
	// ���� post2nfa �������������ĺ����������ת��Ϊ NFA �����ؿ�ʼ״̬
	//
	Start = post2nfa(postfix);
	
	//
	// TODO: �ڴ����Ӵ���
	//
	// ���� Closure �������쿪ʼ״̬�Ħ�-�հ�
	Closure(Start, NFAStateArray, &Count);

	// ���� CreateDFATransform ��������һ��ת��(����ת���ַ�)��
	// Ȼ�󣬵��� CreateDFAState ���������øոմ�����ת���½�һ�� DFA ״̬
	Transform* pTransform = CreateDFATransform('\0', NFAStateArray, Count);
	DFAState* pDFAState = CreateDFAState(pTransform);

	// �� DFA ״̬���뵽 DFA ״̬���Ա���
	pDFA->DFAlist[pDFA->length++] = pDFAState;

	// �������Ա������� DFA ״̬
	for (i=0; i<pDFA->length; i++)
	{
		// ������ i �� DFA ״̬�е����� NFA ״̬
		for (j=0; j<pDFA->DFAlist[i]->NFAStateCount; j++)
		{
			NFAState* NFAStateTemp = pDFA->DFAlist[i]->NFAlist[j];

			// ��� NFA ״̬�ǽ���״̬����ת���ǿ�ת������������ NFA ״̬
			if(NFAStateTemp->Transform == VoidTrans || NFAStateTemp->AcceptFlag == 1)
				continue;

			// ���� Closure �������� NFA ״̬�Ħ�-�հ�
			Closure(NFAStateTemp->Next1, NFAStateArray, &Count);

			// ���� IsTransfromExist �����жϵ�ǰ DFA ״̬��ת���������Ƿ��Ѿ����ڸ� NFA ״̬��ת��
			pTransform = IsTransformExist(pDFA->DFAlist[i], NFAStateTemp->Transform);
			if (pTransform == NULL)
			{
				//�����ڣ����� CreateDFATransform ��������һ��ת�����������ת�����뵽ת�������Ŀ�ʼλ��
				Transform* pTransform = CreateDFATransform(NFAStateTemp->Transform, NFAStateArray, Count);
				DFAState* pDFAState = CreateDFAState(pTransform);
				pTransform->NextTrans=pDFA->DFAlist[i]->firstTran;
				pDFA->DFAlist[i]->firstTran=pTransform;
			}
			else
			{
				//���ڣ����� AddNFAStateArrayToTransform �����Ѧ�-�հ��ϲ����Ѵ��ڵ�ת����
				AddNFAStateArrayToTransform(NFAStateArray, Count, pTransform);
			}
		}

		// ���� DFA ״̬��ת������������ÿ��ת��������Ӧ�� DFA ״̬
		for (pTFCursor = pDFA->DFAlist[i]->firstTran; pTFCursor != NULL; pTFCursor = pTFCursor->NextTrans)
		{
			// ���� NFAStateIsSubset �����ж�ת���е� NFA ״̬�����Ƿ�Ϊĳһ�� DFA ״̬�� NFA ״̬���ϵ��Ӽ�
			int Index = NFAStateIsSubset(pDFA, pTFCursor);
			int k;
			if(Index == -1)
			{
				//�����Ӽ������� CreateDFAState ��������һ���µ� DFA ״̬������ DFA ���Ա���
				DFAState* newDFAState = CreateDFAState(pTFCursor);

				// �� DFA ״̬���뵽 DFA ״̬���Ա���
				pDFA->DFAlist[pDFA->length++] = newDFAState;
				//��ת���� DFAStateIndex ��ֵΪ�¼���� DFA ״̬���±�
				pTFCursor->DFAStateIndex=pDFA->length-1;
			}
			else
			{
				//���Ӽ�����ת���� DFAStateIndex ��ֵΪ Index
				pTFCursor->DFAStateIndex=Index;	
			}
		}
	}
	return pDFA;
}
